//: Playground - noun: a place where people can play

import UIKit

//: ### 创建一个无序集合 set

// empty： 返回一个空的无序集合
// isEmpty：判断集合是否为空
// contains：检查集合中是否包含某元素
// insert：向无序集合中插入一个元素

// 简单实现一下

func empty<Element>() -> [Element] {
    return []
}

func isEmpty<Element>(set: [Element]) -> Bool {
    return set.isEmpty
}

func contains<Element: Equatable>(x:Element, _ set: [Element]) -> Bool {
    return set.contains(x)
}

func insert<Element: Equatable>(x:Element,set: [Element]) -> [Element] {
    return contains(x,set) ? set : set + [x]
}

//: ### 构建二叉搜索树

// 一个没有关联值的叶子 Leaf
// 一个带有三个关联值的节点 Node

indirect enum BinarySearchTree<Element: Comparable> {
    case Leaf
    case Node(BinarySearchTree<Element>,Element,BinarySearchTree<Element>)
}

// 手动构建几棵树

let leaf: BinarySearchTree<Int> = .Leaf
let node: BinarySearchTree<Int> = .Node(leaf,5,leaf)
let node2: BinarySearchTree<Int> = .Node(.Node(leaf,1,leaf),2,.Node(leaf,3,leaf))

// 创建构造器

extension BinarySearchTree {
    init() {
        self = .Leaf
    }
    
    init(_ value: Element) {
        self = .Node(.Leaf,value,.Leaf)
    }
}

// 我们的 BinarySearchTree是递归的，所以基于他的函数也是递归的

extension BinarySearchTree {
    var count: Int {
        switch self {
        case .Leaf:
            return 0
        case let .Node(left, _, right):
            return 1 + left.count + right.count
        }
    }
}

leaf.count
node.count

// 计算树中所有元素组成的数组

extension BinarySearchTree {
    var elements: [Element] {
        switch self {
        case .Leaf:
            return []
        case let .Node(left,x,right):
            return left.elements + [x] + right.elements
        }
    }
}
leaf.elements
node.elements
node2.elements

// 检测一棵树是否为空

extension BinarySearchTree {
    var empty: Bool {
        if case .Leaf = self {
            return true
        }
        return false
    }
}


// 判断BinarySearchTree 是不是一个一颗二叉搜索树

extension BinarySearchTree where Element: Comparable {
    var isBST: Bool {
        switch self {
        case .Leaf:
            return true
        case let .Node(left,x,right):
            return left.elements.all{ y in y < x }
                && right.elements.all{ y in y > x }
                && left.isBST
                && right.isBST
        }
    }
}

extension SequenceType {
    func all(predicate: Generator.Element-> Bool) -> Bool {
        for x in self where !predicate(x) {
            return false
        }
        return true
    }
}

// contains 方法 二分法加限制：
// 限制一：左子节点 < 根节点
// 限制二：右子节点 > 根节点

extension BinarySearchTree {func contains(x: Element) -> Bool {
        switch self {
        case .Leaf:
            return false
        case let .Node(_, y, _) where x == y:
            return true
        case let .Node(left, y, _) where x < y:
            return left.contains(x)
        case let .Node(_, y, right) where x > y:
            return right.contains(x)
        default:
            fatalError("未知错误")
        }
    }
}

// 由于 self 参与运算，所以 func 前面要添加 mutating
// 协议与结构体 如果需要修改自己的成员变量需要在 func 前面添加 mutating 而 class 默认可以随意修改自己的成员变量不需要添加。
extension BinarySearchTree {
    mutating func insert(x: Element){
        switch self {
        case .Leaf:
            self = BinarySearchTree(x)
        case .Node(var left,let y, var right):
            if x < y { left.insert(x) }
            if x > y { right.insert(x) }
            self = .Node(left, y, right)
        }
    }
}



//: ### 牛逼的字典树

struct Trie<Element: Hashable> {
    let isElement: Bool
    let children: [Element: Trie<Element>]
}

// 构造函数

extension Trie {
    init() {
        isElement = false
        children = [:]
    }
}

// 将字典树展平为一个包含所有元素的数组

extension Trie {
    var elements: [[Element]] {
        var result: [[Element]] = isElement ? [[]] : []
        for (key, value) in children {
            result += value.elements.map{ [key] + $0}
        }
        return result
    }
}

// 实现递归数组
// 将一个数组返回 第一个元素 以及剩下的元素组成的数组
extension Array {
    var decompose:(Element,[Element])? {
        return isEmpty ? nil : (self[startIndex],Array(self.dropFirst()))
    }
}

func sum(xs:[Int]) -> Int {
    guard let (head, tail) = xs.decompose else { return 0 }
    return head + sum(tail)
}

let intArray = [1,2,3,4,5]
sum(intArray)




extension Trie {
    func lookup(key: [Element]) -> Bool {
        guard let (head,tail) =  key.decompose else { return isElement }
        guard let subtrie = children[head] else { return  false }
        return subtrie.lookup(tail)
    }
}

// 尝试实例化一个 字典
//let trie = Trie(isElement: true, children: ["C" : Trie.init()])

// 给定一个前缀返回一个包含所有匹配元素的数组

extension Trie {
    func withPrefix(prefix: [Element]) -> Trie<Element>? {
        guard let (head, tail) = prefix.decompose else { return self }
        guard let remainder = children[head] else { return nil }
        return remainder.withPrefix(tail)
    }
}

// 定义 autocomplete 函数

extension Trie {
    func autocomplete(key: [Element]) -> [[Element]] {
        return withPrefix(key)?.elements ?? []
    }
}




// 创建一个只含有一个元素的字典树

extension Trie {
    init(_ key: [Element]) {
        if let (head, tail) = key.decompose {
            let children = [head: Trie(tail)]
            self = Trie(isElement: false, children: children)
        } else {
            self = Trie(isElement: true, children: [:])
        }
    }
}

// 创建插入函数来填充字典树

extension Trie {
    func insert(key: [Element]) -> Trie<Element> {
        guard let (head, tail) = key.decompose else {
            return Trie(isElement: true, children: children)
        }
        var newChildren = children
        if let nextTrie = children[head] {
            newChildren[head] = nextTrie.insert(tail)
        } else {
            newChildren[head] = Trie(tail)
        }
        return Trie(isElement: isElement,children: newChildren)
    }
}

//: ### 字符串字典树

func buildStringTrie(words: [String]) -> Trie<Character> {
    let emptyTrie = Trie<Character>()
    return words.reduce(emptyTrie){ trie, word in trie.insert(Array(word.characters)) }
}

func autocompleteString(knownWords: Trie<Character>, word: String) -> [String] {
    let chars = Array(word.characters)
    let completed = knownWords.autocomplete(chars)
    return completed.map{ chars in word + String(chars) }
}

let contents = ["cat", "car", "cart", "dog"]
let trieOfWords = buildStringTrie(contents)
trieOfWords.isElement
trieOfWords.elements
autocompleteString(trieOfWords, word: "car")


let stringArray = ["a","r","t"]

let i = stringArray.map{["c"] + [$0]}
print(i)








